package 双指针;

/**
 * @author TTDB
 * @create 2025/9/13
 */
public class trap {
    public int trap(int[] height) {
        //左边最大和右边最大
        int n = height.length;
        int[] pre = new int[n];
        pre[0] = height[0];
        int[] aft = new int[n];
        aft[n-1] = height[n -1];
        for(int i = 1; i < n; i++){
            pre[i] = Math.max(pre[i-1], height[i]);
        }
        for(int i = n - 2; i >= 0; i--){
            aft[i] = Math.max(aft[i + 1], height[i]);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res += Math.min(pre[i], aft[i])-height[i];
        }
        return res;
    }
}
